package com.linkedin.dagli.util.collection;

import it.unimi.dsi.fastutil.BigList;
import it.unimi.dsi.fastutil.Size64;
import it.unimi.dsi.fastutil.objects.Object2LongMap;
import it.unimi.dsi.fastutil.objects.Object2LongOpenHashMap;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.Optional;
import java.util.function.Function;
import java.util.function.Supplier;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;


/**
 * Utility methods for manipulating {@link Iterable}s such as {@link java.util.List}s and {@link java.util.Collection}s.
 */
public abstract class Iterables {
  private Iterables() { }

  /**
   * Convenience method for streaming the elements of the iterable.
   *
   * If the iterable is of a type recognized as streamable, its {@code stream()} method will be used.  Otherwise, a
   * stream will be created using the iterable's spliterator.
   *
   * @param iterable the iterable to stream
   * @param <T> the type of object contained by the iterable
   * @return a stream over the contents of the iterable
   */
  public static <T> Stream<T> stream(Iterable<T> iterable) {
    if (iterable instanceof Collection) {
      return ((Collection<T>) iterable).stream();
    }
    return StreamSupport.stream(iterable.spliterator(), false);
  }

  /**
   * Checks if an iterable is sorted according to the given comparator.
   *
   * @param iterable the iterable to check
   * @param comparator a comparator providing an ordering over the items in the iterable
   * @param <T> the type of item
   * @return true iff the iterable is sorted according to the given comparator
   */
  public static <T> boolean isSorted(Iterable<? extends T> iterable, Comparator<? super T> comparator) {
    return isSorted(iterable.iterator(), comparator);
  }

  /**
   * Checks if an iterator is sorted according to the given comparator.
   *
   * @param iterator the iterator to check
   * @param comparator a comparator providing an ordering over the items in the iterator
   * @param <T> the type of item
   * @return true iff the iterator is sorted according to the given comparator
   */
  public static <T> boolean isSorted(Iterator<? extends T> iterator, Comparator<? super T> comparator) {
    if (iterator.hasNext()) {
      T last = iterator.next();
      while (iterator.hasNext()) {
        T current = iterator.next();
        if (comparator.compare(last, current) > 0) {
          return false;
        }
        last = current;
      }
    }

    return true;
  }

  /**
   * Checks if two iterables contain <strong>exactly</strong> the same elements in the same order; that is, every
   * element generated by the two iterables matches according to reference equality (== operator).
   *
   * @param iterable1 the first iterable to compare
   * @param iterable2 the second iterable to compare
   * @return true if the iterables both have exactly the same elements (as determined by ==) in the same order
   */
  public static boolean elementsAreReferenceEqual(Iterable<?> iterable1, Iterable<?> iterable2) {
    // check sizes if it is cheap to do so
    if (hasKnownSize(iterable1) && hasKnownSize(iterable2) && size64(iterable1) != size64(iterable2)) {
      return false;
    }

    Iterator<?> iterator2 = iterable2.iterator();
    for (Object element : iterable1) {
      if (!iterator2.hasNext()) {
        return false; // iterable2 has too few elements
      } else if (element != iterator2.next()) {
        return false; // element mismatch
      }
    }
    return !iterator2.hasNext(); // the two iterables must be equal iff iterator2 has no more elements
  }

  /**
   * Creates a hash for the elements in the iterable.  This hash code is sensitive to the ordering of the elements and
   * matches the implementation mandated for {@link java.util.List#hashCode()}s.
   *
   * @param iterable the iterable whose elements are to be hashed
   * @return a hash code corresponding to the ordered elements of the iterable
   */
  public static int hashCodeOfOrderedElements(Iterable<?> iterable) {
    int result = 1;

     for (Object o : iterable) {
       result = 31 * result + Objects.hashCode(o);
     }

     return result;
  }

  /**
   * Checks if two iterables contain the same elements (as determined by {@link Objects#equals(Object, Object)} in the
   * same order.
   *
   * @param iterable1 the first iterable to compare
   * @param iterable2 the second iterable to compare
   * @return true if the iterables both have the same elements (as determined by {@link Objects#equals(Object, Object)})
   *         in the same order
   */
  public static boolean elementsAreEqual(Iterable<?> iterable1, Iterable<?> iterable2) {
    // check sizes if it is cheap to do so
    if (hasKnownSize(iterable1) && hasKnownSize(iterable2) && size64(iterable1) != size64(iterable2)) {
      return false;
    }

    Iterator<?> iterator2 = iterable2.iterator();
    for (Object element : iterable1) {
      if (!iterator2.hasNext()) {
        return false; // iterable2 has too few elements
      } else if (!Objects.equals(element, iterator2.next())) {
        return false; // element mismatch
      }
    }
    return !iterator2.hasNext(); // the two iterables must be equal iff iterator2 has no more elements
  }

  /**
   * Checks if two iterables share the same elements (and, if there are duplicates, they share the duplicate elements
   * in the same quantity).
   *
   * @param iterable1 the first collection of elements
   * @param iterable2 the second collection of elements
   * @return true if both iterables contain the same elements
   */
  public static boolean sameMultisetOfElements(Iterable<?> iterable1, Iterable<?> iterable2) {
    // check the size if it is cheap to do so
    if (hasKnownSize(iterable1) && hasKnownSize(iterable2)) {
      if (size64(iterable1) != size64(iterable2)) {
        return false;
      }
    }

    // we use this max size to avoid tiggering FastUtil's "too large" error; unfortunately this is tied to FastUtil's
    // "hidden" rule against creating arrays with more than (1 << 30) elements, which could conceivably change in the
    // future (but probably won't get smaller as that would be a breaking change)
    final int maxInitialSize = (int) Math.floor((1 << 30) * Object2LongOpenHashMap.DEFAULT_LOAD_FACTOR);
    Object2LongOpenHashMap<Object> multiset = new Object2LongOpenHashMap<>(
        hasKnownSize(iterable1) ? (int) Math.min(maxInitialSize, size64(iterable1)) : 8);

    for (Object item : iterable1) {
      multiset.addTo(item, 1);
    }
    for (Object item : iterable2) {
      multiset.addTo(item, -1);
    }

    it.unimi.dsi.fastutil.longs.LongIterator iter = multiset.values().iterator();
    while (iter.hasNext()) {
      if (iter.nextLong() != 0) {
        return false;
      }
    }
    return true;
  }

  /**
   * Gets the {@code index} item from an {@link Iterable} according to its iteration order.  Note that for some
   * iterables (e.g. {@link java.util.HashMap}) the iteration order is not fixed.
   *
   * For {@link List}s and {@link BigList}s, the {@code get(...)} method (which, for "random-access" lists, is
   * constant-time) is used.  For other iterables, the items must be iterated, requiring time linear in {@code index}.
   * Consequently, this method should generally not be used to repeatedly fetch multiple items in, e.g. a loop.
   *
   * @param iterable the iterable from which an item is sought
   * @param index the 0-based index of the desired item in the iterable's iteration order
   * @param <T> the type of item contained in the iterable
   * @return the required item from the iterable
   * @throws IndexOutOfBoundsException if {@code index >= size64(iterable)}
   * @throws NoSuchElementException if {@code index >= size64(iterable)}
   */
  public static <T> T get(Iterable<T> iterable, long index) {
    if (iterable instanceof BigList) {
      return ((BigList<T>) iterable).get(index);
    } else if (iterable instanceof List) {
      return ((List<T>) iterable).get(Math.toIntExact(index));
    }

    return get(iterable.iterator(), index);
  }

  /**
   * Gets the n'th item returned by the provided iterator.
   *
   * The first element returned by the iterator corresponds to {@code n == 0}.
   *
   * @param iterator the iterator from which the given element should be obtained
   * @param n the item to get; 0 corresponds to the first element returned by the iterator
   * @param <T> the type of element enumerated by the iterator
   * @return the (0-based) n'th item in the iterator
   * @throws NoSuchElementException if the iterator contains fewer than (n+1) elements
   */
  public static <T> T get(Iterator<T> iterator, long n) {
    for (long i = 0; i < n; i++) {
      iterator.next();
    }

    return iterator.next();
  }

  /**
   * Calculates the size of an iterable, using (in order of preference) {@link Size64#size64()},
   * {@link Collection#size()}, or iterating over its members.
   *
   * @param iterable the iterable whose elements will be counted
   * @return the number of elements in the iterable
   */
  public static long size64(Iterable<?> iterable) {
    if (iterable instanceof Size64) {
      return ((Size64) iterable).size64();
    } else if (iterable instanceof Collection) {
      return ((Collection<?>) iterable).size();
    } else {
      return countElements(iterable);
    }
  }

  /**
   * If the size of a provided {@link Iterable} can be determined by {@link #size64(Iterable)} "easily", returns that
   * size.  Otherwise returns the provided default value.
   *
   * This can be useful when an exact size is preferred where it is cheaply available, but not worth iterating over all
   * the elements in the iterable to find otherwise.
   *
   * @param iterable the iterable whose size is sought
   * @param defaultSize the default size to return (possibly negative) if the true size would require iterating over all
   *                    the elements of {@code iterable}
   * @return the true size of iterable or the provided default size
   */
  public static long size64OrDefault(Iterable<?> iterable, long defaultSize) {
    return hasKnownSize(iterable) ? size64(iterable) : defaultSize;
  }

  /**
   * Checks if the size of a provided {@link Iterable} can be determined by {@link #size64(Iterable)} "easily";
   * specifically, whether it has a size that can be obtained without iterating over all the items in the iterable.
   *
   * @param iterable the iterable whose elements will be counted
   * @return true if the iterable's size can be "easily" determined; false if {@link #size64(Iterable)} would need to
   *         iterate over all of its elements in order to count them.
   */
  public static boolean hasKnownSize(Iterable<?> iterable) {
    return (iterable instanceof Size64) || (iterable instanceof Collection);
  }

  /**
   * Counts the number of elements in an iterable by iterating over its members (this may be expensive).
   *
   * @param iterable the iterable whose elements should be counted
   * @return the number of elements in the iterable
   */
  private static long countElements(Iterable<?> iterable) {
    long[] count = new long[1];
    iterable.forEach(i -> count[0]++);
    return count[0];
  }

  /**
   * Convenience method that prepends the provided value(s) to a given list (without modifying this original list),
   * returning a new ArrayList.
   *
   * @param list not modified; the returned list will contain the prepended values follow by the values in this list
   * @param values the prepended values
   * @param <T> the type of element in the list
   * @return a new ArrayList with the provided values prepended
   */
  @SafeVarargs
  public static <T> ArrayList<T> prepend(Iterable<? extends T> list, T... values) {
    ArrayList<T> result = new ArrayList<>(Math.toIntExact(size64(list) + values.length));

    Collections.addAll(result, values);
    addAll(result, list);

    return result;
  }



  /**
   * Convenience method that appends the provided value(s) to a given list (without modifying this original list),
   * returning a new ArrayList.
   *
   * @param list not modified, but the returned list will contain this list's values followed by the appended values
   * @param values the appended values
   * @param <T> the type of element in the list
   * @return a new ArrayList with the provided values appended
   */
  @SafeVarargs
  public static <T> ArrayList<T> append(Iterable<? extends T> list, T... values) {
    ArrayList<T> result = new ArrayList<>(Math.toIntExact(size64(list) + values.length));

    addAll(result, list);
    Collections.addAll(result, values);

    return result;
  }

  /**
   * Analogous to {@link Collection#addAll(Collection)}, but accepts an {@link Iterable} of added values rather than
   * a collection.  Note that {@link Collections#addAll(Collection, Object[])} provides another alternative accepting
   * an array of added values.
   *
   * @param collection the collection to which values will be added
   * @param values the values to add
   * @param <T> the type of value to add
   * @return true iff the collection was modified by this addition operation (may not be the case with, e.g. sets)
   */
  public static <T> boolean addAll(Collection<? super T> collection, Iterable<T> values) {
    if (values instanceof Collection) { // if values is a collection, there's an existing method we can use
      return collection.addAll((Collection<T>) values);
    } else { // values is not a collection
      boolean result = false;
      for (T value : values) {
        result |= collection.add(value);
      }
      return result;
    }
  }

  /**
   * Finds the index of the element comparing highest/greatest/maximum in a supplied list of {@link Comparable} items.
   * In the event of a tie, the lowest index of a maximal element is returned.
   *
   * See also {@link java.util.Collections#max(java.util.Collection)} which finds the maximum item's
   * <strong>value</strong> rather than its index.
   *
   * @param iterable the list of items to search (index 0 is assumed to correspond to the first item)
   * @param <T> the type of (comparable) item being compared
   * @return -1 if the iterable contains no items; otherwise, the index of the maximum item in the iterable
   */
  public static <T extends Comparable<? super T>> int argMax(Iterable<? extends T> iterable) {
    return argMax(iterable, Comparator.naturalOrder());
  }

  /**
   * Finds the index of the element comparing highest/greatest/maximum in a supplied list of {@link Comparable} items.
   * In the event of a tie, the lowest index of a maximal element is returned.
   *
   * See also {@link java.util.Collections#max(java.util.Collection)} which finds the maximum item's
   * <strong>value</strong> rather than its index.
   *
   * @param iterator the list of items to search (index 0 is assumed to correspond to the first item)
   * @param <T> the type of (comparable) item being compared
   * @return -1 if the iterator contains no items; otherwise, the index of the maximum item in the iterable
   */
  public static <T extends Comparable<? super T>> int argMax(Iterator<? extends T> iterator) {
    return argMax(iterator, Comparator.naturalOrder());
  }

  /**
   * Finds the index of the element comparing highest/greatest/maximum in a supplied list of items.  In the event of a
   * tie, the lowest index of a maximal element is returned.
   *
   * See also {@link java.util.Collections#max(java.util.Collection, Comparator)} which finds the maximum
   * item's<strong>value</strong> rather than its index.
   *
   * @param iterable the list of items to search (index 0 is assumed to correspond to the first item)
   * @param comparator a {@link Comparator} used to compare the items
   * @param <T> the type of item being compared
   * @return -1 if the iterable contains no items; otherwise, the index of the maximum item in the iterable
   */
  public static <T> int argMax(Iterable<? extends T> iterable, Comparator<T> comparator) {
    return argMax(iterable.iterator(), comparator);
  }

  /**
   * Finds the index of the element comparing highest/greatest/maximum in a supplied list of items.  In the event of a
   * tie, the lowest index of a maximal element is returned.
   *
   * See also {@link java.util.Collections#max(java.util.Collection, Comparator)} which finds the maximum
   * item's<strong>value</strong> rather than its index.
   *
   * @param iterator the list of items to search (index 0 is assumed to correspond to the first item)
   * @param comparator a {@link Comparator} used to compare the items
   * @param <T> the type of item being compared
   * @return -1 if the iterator contains no items; otherwise, the index of the maximum item in the iterable
   */
  public static <T> int argMax(Iterator<? extends T> iterator, Comparator<T> comparator) {
    if (!iterator.hasNext()) {
      return -1;
    }

    int maxIndex = 0;
    T maxValue = iterator.next();
    int currentIndex = 0;

    while (iterator.hasNext()) {
      T currentValue = iterator.next();
      currentIndex++;

      if (comparator.compare(maxValue, currentValue) < 0) {
        maxValue = currentValue;
        maxIndex = currentIndex;
      }
    }

    return maxIndex;
  }

  /**
   * Maps the elements of an iterate using the given mapping function, returning the mapped items as a new list.
   *
   * @param iterable the iterable whose elements should be mapped
   * @param mapper the mapping function
   * @param <V> the type of items in the iterable
   * @param <R> the type of items in the returned list
   * @return a new list containing the mapped items
   */
  public static <V, R> List<R> map(Iterable<? extends V> iterable, Function<? super V, ? extends R> mapper) {
    ArrayList<R> result = new ArrayList<>(Math.toIntExact(size64(iterable)));
    for (V element : iterable) {
      result.add(mapper.apply(element));
    }
    return result;
  }

  /**
   * Returns the most common item in a given iterable (with ties broken arbitrarily.)
   *
   * @param iterable an iterable providing the items whose mode is sought
   * @param <T> the type of item in the iterable
   * @return an {@link Optional} that will contain the mode of the items the iterable if the iterable is non-empty
   */
  public static <T> Optional<T> mode(Iterable<? extends T> iterable) {
    return mode(iterable.iterator());
  }

  /**
   * Returns the most common item in a given iterator (with ties broken arbitrarily.)
   *
   * @param iterator an iterator providing the items whose mode is sought
   * @param <T> the type of item in the iterator
   * @return an {@link Optional} that will contain the mode of the items the iterator if the iterator is non-empty
   */
  public static <T> Optional<T> mode(Iterator<? extends T> iterator) {
    return countItems(iterator).object2LongEntrySet()
        .stream()
        .max(Comparator.comparingLong(Object2LongMap.Entry::getLongValue))
        .map(Object2LongMap.Entry::getKey);
  }

  /**
   * Counts the number of times each item occurs in an iterable, returning these counts as a map.
   *
   * @param iterable an iterable providing the items to count
   * @param <T> the type of item to count
   * @return a map from items to their counts
   */
  public static <T> Object2LongMap<T> countItems(Iterable<? extends T> iterable) {
    return countItems(iterable.iterator());
  }

  /**
   * Counts the number of times each item occurs in an iterator, returning these counts as a map.
   *
   * @param iterator an iterator providing the items to count
   * @param <T> the type of item to count
   * @return a map from items to their counts
   */
  public static <T> Object2LongMap<T> countItems(Iterator<? extends T> iterator) {
    Object2LongOpenHashMap<T> result = new Object2LongOpenHashMap<>();
    countItems(iterator, result);
    return result;
  }

  /**
   * Counts the number of times each item occurs in an iterator, incrementing the count per item in the supplied
   * {@link Object2LongMap}.
   *
   * @param iterator the iterator of items to count
   * @param counts a map whose entries will be incremented by the number of times each item has been seen (counting
   *               begins at the existing values [or {@link Object2LongOpenHashMap#defaultReturnValue()}, if no entry
   *               already exists for an item], and any values for items not seen in the iterator will not be modified)
   * @param <T> the type of item in the iterator
   */
  private static <T> void countItems(Iterator<? extends T> iterator, Object2LongOpenHashMap<? super T> counts) {
    while (iterator.hasNext()) {
      counts.addTo(iterator.next(), 1);
    }
  }

  /**
   * Creates a new list containing the same elements as the provided original sequence, except with a new value at the
   * specified position.  The original sequence is unmodified.
   *
   * @param iterable the original sequence of items; will not be modified
   * @param replacementIndex the 0-based position of the item to replace; must be less than the number of items in the
   *                         original sequence
   * @param replacement the replacement item to be placed at {@code replacementIndex} in the returned list
   * @param <T> the type of element in the sequence
   * @return a new list containing the same elements as the provided original sequence, except with a new value at the
   *         specified position
   */
  public static <T> ArrayList<T> replaceAtIndex(Iterable<T> iterable, int replacementIndex, T replacement) {
    return replaceAtIndex(iterable.iterator(), replacementIndex, replacement,
        hasKnownSize(iterable) ? Math.toIntExact(size64(iterable)) : 8);
  }

  /**
   * Creates a new list containing the same elements as the provided original sequence, except with a new value at the
   * specified position.  The original sequence is unmodified.
   *
   * @param iterator the original sequence of items; will not be modified
   * @param replacementIndex the 0-based position of the item to replace; must be less than the number of items in the
   *                         original sequence
   * @param replacement the replacement item to be placed at {@code replacementIndex} in the returned list
   * @param <T> the type of element in the sequence
   * @return a new list containing the same elements as the provided original sequence, except with a new value at the
   *         specified position
   */
  public static <T> ArrayList<T> replaceAtIndex(Iterator<T> iterator, int replacementIndex, T replacement) {
    return replaceAtIndex(iterator, replacementIndex, replacement, 8);
  }

  /**
   * Creates a new list containing the same elements as the provided original sequence, except with a new value at the
   * specified position.  The original sequence is unmodified.
   *
   * @param iterator the original sequence of items; will not be modified
   * @param replacementIndex the 0-based position of the item to replace; must be less than the number of items in the
   *                         original sequence
   * @param replacement the replacement item to be placed at {@code replacementIndex} in the returned list
   * @param <T> the type of element in the sequence
   * @param sizeGuess a guess at how many items the iterator will return
   * @return a new list containing the same elements as the provided original sequence, except with a new value at the
   *         specified position
   */
  private static <T> ArrayList<T> replaceAtIndex(Iterator<T> iterator, int replacementIndex, T replacement,
      int sizeGuess) {
    ArrayList<T> result = new ArrayList<>(sizeGuess);
    iterator.forEachRemaining(result::add);
    result.set(replacementIndex, replacement);
    return result;
  }

  /**
   * Creates a new list containing the same elements as the provided original sequence, except with a new value at the
   * specified position.  The original sequence is unmodified.
   *
   * @param iterable the original sequence of items; will not be modified
   * @param replacementIndex the 0-based position of the item to replace; must be less than the number of items in the
   *                         original sequence
   * @param replacement the replacement item to be placed at {@code replacementIndex} in the returned list
   * @param <T> the type of element in the sequence
   * @return a new list containing the same elements as the provided original sequence, except with a new value at the
   *         specified position
   */
  public static <T> ArrayList<T> replaceAtIndex(Collection<T> iterable, int replacementIndex, T replacement) {
    ArrayList<T> result = new ArrayList<>(iterable);
    result.set(replacementIndex, replacement);
    return result;
  }

  /**
   * Creates a new {@link ArrayList} containing the items in the provided iterable.
   *
   * @param iterable the iterable whose items should be placed in the returned list
   * @param <T> the type of item in the list
   * @return a new {@link ArrayList} containing the items in the provided iterable
   */
  public static <T> ArrayList<T> newArrayList(Iterable<? extends T> iterable) {
    return concatenate(iterable);
  }

  /**
   * Creates a new {@link ArrayList} containing the items in the provided iterator.  This will exhaust the iterator.
   *
   * @param iterator the iterator whose items should be placed in the returned list
   * @param <T> the type of item in the list
   * @return a new {@link ArrayList} containing the items in the provided iterator
   */
  public static <T> ArrayList<T> newArrayList(Iterator<? extends T> iterator) {
    return concatenate(8, iterator);
  }

  /**
   * Concatenates the provided collections into a single list.
   *
   * @param collections the collections to concatenate
   * @param <T> the type of element in the collections
   * @return a new concatenated list of all the items in the provided collections
   */
  @SafeVarargs
  public static <T> ArrayList<T> concatenate(Collection<? extends T>... collections) {
    int size = 0;
    for (Collection<? extends T> collection : collections) {
      size += collection.size();
    }
    ArrayList<T> result = new ArrayList<>(size);
    for (Collection<? extends T> collection : collections) {
      result.addAll(collection);
    }
    return result;
  }

  /**
   * Concatenates the provided iterables into a single list.
   *
   * @param collections the iterables to concatenate
   * @param <T> the type of element in the iterables
   * @return a new concatenated list of all the items in the provided iterables
   */
  @SafeVarargs
  public static <T> ArrayList<T> concatenate(Iterable<? extends T>... collections) {
    int size = 0;
    for (Iterable<? extends T> collection : collections) {
      size += size64OrDefault(collection, 2);
    }
    ArrayList<T> result = new ArrayList<>(size);
    for (Iterable<? extends T> collection : collections) {
      collection.forEach(result::add);
    }
    return result;
  }

  /**
   * Concatenates the items provided by the given iterators into a single list (and exhausts the iterators).
   *
   * @param concatenatedSizeGuess a guess at how many items there are in all provided iterators; this is used as the
   *                              initial capacity of the returned {@link ArrayList}
   * @param collections the iterators to concatenate
   * @param <T> the type of element in the iterators
   * @return a new concatenated list of all the items in the provided iterators
   */
  @SafeVarargs
  public static <T> ArrayList<T> concatenate(int concatenatedSizeGuess, Iterator<? extends T>... collections) {
    ArrayList<T> result = new ArrayList<>(concatenatedSizeGuess);
    for (Iterator<? extends T> collection : collections) {
      collection.forEachRemaining(result::add);
    }
    return result;
  }

  /**
   * Lazily concatenates collections supplied by the provided {@code iterableSuppliers}; the supplied iterables are
   * cached, so no supplier will be called more than once by the returned instance.  The suppliers are only called
   * when--and if--they are needed.
   *
   * @param iterableSuppliers methods returning iterables
   * @param <T> the type of item contained within the iterables
   * @return an iterable that enumerates the concatenated sequence of items provided by the {@code iterableSuppliers}
   */
  @SuppressWarnings("unchecked") // generic array never escapes anonymous class
  public static <T> Iterable<T> lazyConcatenate(Supplier<? extends Iterable<? extends T>>... iterableSuppliers) {
    return new Iterable<T>() {
      Iterable<? extends T>[] _cache = new Iterable[iterableSuppliers.length];

      @Override
      public Iterator<T> iterator() {
        return new Iterator<T>() {
          int _currentIterableIndex = -1;
          Iterator<T> _currentIterator = Collections.emptyIterator();

          @Override
          public boolean hasNext() {
            if (_currentIterableIndex == iterableSuppliers.length) {
              return false;
            }
            while (!_currentIterator.hasNext()) {
              _currentIterableIndex++;
              if (_currentIterableIndex == iterableSuppliers.length) {
                return false;
              }
              if (_cache[_currentIterableIndex] == null) {
                _cache[_currentIterableIndex] = iterableSuppliers[_currentIterableIndex].get();
              }
              _currentIterator = (Iterator<T>) _cache[_currentIterableIndex].iterator();
            }

            return true;
          }

          @Override
          public T next() {
            if (!hasNext()) {
              throw new NoSuchElementException();
            }
            return _currentIterator.next();
          }
        };
      }
    };
  }
}
